/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.controller;

import java.util.ArrayList;
import java.util.PriorityQueue;

import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.util.TspUtil;

/**
 * @author minho kim
 * 
 */
public class IterativeDeepeningSearch extends SearchAlgorithm {
	private PriorityQueue<CityPath> frontier;
	private ArrayList<CityPath> goalCityPathList = new ArrayList<CityPath>();
	private int limitStep = 0;
//	private double[] limitUnitTable = 
//		{ 0.0, 0.05, 0.05, 0.05, 0.05, 0.1, 0.1, 0.1, 0.1, 0.1, 
//		  0.2, 0.2, 0.2, 0.3, 0.3, 0.3, 0.3, 0.4, 0.4, 0.4,
//		  0.5, 0.5, 0.1, 0.1, 0.1, 0.6, 0.6, 0.7, 0.7, 0.7,
//		  0.7, 0.7, 0.7, 0.7, 0.7, 0.7, 0.7, 0.7, 0.7, 0.7,
//		  0.8, 0.8, 0.8, 0.8, 0.8, 0.9, 0.9, 0.9, 0.9, 0.9,
//		  1.0, 1.0, 1.0, 1.0, 1.0, 1.1, 1.1, 1.1, 1.1, 1.1,
//		  1.2, 1.2, 1.2, 1.2, 1.2, 1.3, 1.3, 1.3, 1.3, 1.3,
//		  1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5
//		};

	/*
	 * (non-Javadoc)
	 * 
	 * @see kaist.sep502.tsp.controller.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {
		Solution solution = new Solution();
		solution.expandedNodeCount = 0;
		solution.startStopWatch();

		//double limitUnit = limitUnitTable[Problem.getCitySize()];
		double limitUnit = 0.2;
		double limitCost = new GreedySearch().search().getGoalCityPath()
				.getPathCost() - limitUnit;
		Heuristic heuristic;

		frontier = new PriorityQueue<CityPath>(20000000);
		CityPath cityPath = new CityPath(Problem.getDepartureCityNo());
		frontier.add(cityPath);
		int citySize = Problem.getCitySize();
		
		for (; limitCost > 0; limitCost -= 0.1, limitStep++) {
			
			
			
			System.out.println("LIMIT COST: " + limitCost );
			
			
			
			while (frontier.size() > 0) {
				solution.expandedNodeCount++;
				cityPath = frontier.poll();
				
				for (int i = 0; i < citySize; i++) {
					// 이미 들린 도시이면 제외
					if (visited(cityPath, i))
						continue;

					// 도시 경로 정보를 만든다.
					CityPath newCityPath = cityPath.clone();
					
					heuristic = heuristicAlgorithm.getHx(newCityPath, i);
					newCityPath.set(heuristic.cityNo, heuristic.hx);
					
//					System.out.println(newCityPath);
					
					// Goal에 맞는지 확인.
					if (Problem.checkGoal(newCityPath)) {
						goalCityPathList.add(newCityPath);
					} else if (newCityPath.getPathCost() <= limitCost) {
						frontier.add(newCityPath);
					}
				}
			}
		}

		double minPathCost = Double.MAX_VALUE;
		int indexOfMin = -1;
		for (int i = 0; i < goalCityPathList.size(); i++) {
			if (goalCityPathList.get(i).getPathCost() < minPathCost) {
				minPathCost = goalCityPathList.get(i).getPathCost();
				indexOfMin = i;
			}
		}

		if (indexOfMin >= 0) {
			solution.setGoalCityPath(goalCityPathList.get(indexOfMin));
			solution.setSuccess(true);
			solution.stopStopWatch();
		}
		
		System.out.println("LIMIT STEP:" +  limitStep);

		return solution;
	}

	private boolean visited(CityPath cityPath, int cityNo) {
		if (cityPath.index == Problem.getCitySize() && cityNo == 0) {
			return false;
		}
		
		int cityPathIndex = cityPath.index;
		int tourHistory[] = cityPath.tourHistory;
		for (int j = 0; j < cityPathIndex; j++) {
			if (cityNo == tourHistory[j]) {
				return true;
			}
		}

		return false;
	}

}
